      1  import java.util.ArrayList;

      2  import java.util.Arrays;

      3  import java.util.Collections;

      4

      5  /**

      6     This program shows how a more efficient algorithm can greatly speed up

      7     the task of finding the most frequent element in an array.

      8  */

      9  public class MostFrequent

     10  {

     11     public static void main(String[] args)

     12     {

     13        ArrayList<Integer> values = new ArrayList<Integer>();

     14        int k = 300;

     15        // Adds one times 1, two times 2, three times 3, ... , k times k

     16        for (int i = 1; i <= k; i++)

     17        {

     18           for (int j = 1; j <= i; j++)

     19           {

     20              values.add(i);

     21           }

     22        }

     23        // This method shuffles the array list randomly

     24        Collections.shuffle(values);

     25

     26        StopWatch timer = new StopWatch();

     27        int[] a = new int[values.size()];

     28

     29        // Copies the values into an array and runs the first version

     30        // of the algorithm

     31        for (int i = 0; i < a.length; i++) { a[i] = values.get(i); }

     32        timer.start();

     33        int result = mostFrequent1(a);

     34        timer.stop();

     35        System.out.println(result);

     36        System.out.println("Expected: " + k);

     37        System.out.println("Elapsed time: "

     38              + timer.getElapsedTime() + " milliseconds");

     39

     40        // Copies the same values and runs the second version

     41        for (int i = 0; i < a.length; i++) { a[i] = values.get(i); }

     42        timer.reset();

     43        timer.start();

     44        result = mostFrequent2(a);

     45        timer.stop();

     46        System.out.println(result);

     47        System.out.println("Expected: " + k);

     48        System.out.println("Elapsed time: "

     49              + timer.getElapsedTime() + " milliseconds");

     50     }

     51

     52     /**

     53        Returns the most frequently occurring value in an array.

     54        @param a an array

     55        @return the most frequently occuring value in a

     56     */

     57     public static int mostFrequent1(int[] a)

     58     {

     59        int[] counts = new int[a.length];

     60        for (int i = 0; i < a.length; i++) // O(n*n)

     61        {

     62           counts[i] = count(a, a[i]); // O(n) in each iteration

     63        }

     64

     65        int highestFrequency = max(counts); // O(n)

     66        int highestFrequencyIndex = search(counts, highestFrequency); // O(n)

     67        return a[highestFrequencyIndex];

     68     }

     69

     70     /**

     71        Returns the most frequently occurring value in an array.

     72        @param a an array

     73        @return the most frequently occuring value in a

     74     */

     75     public static int mostFrequent2(int[] a)

     76     {

     77        Arrays.sort(a); // O(n log(n))

     78        int[] counts = new int[a.length];

     79

     80        int count = 0;

     81        for (int i = 0; i < a.length; i++) // O(n)

     82        {

     83           count++;

     84           if (i == a.length - 1 || a[i] != a[i + 1])

     85           {

     86              counts[i] = count;

     87              count = 0;

     88           }

     89        }

     90

     91        int highestFrequency = max(counts); // O(n)

     92        int highestFrequencyIndex = search(counts, highestFrequency); // O(n)

     93        return a[highestFrequencyIndex];

     94     }

     95

     96     /**

     97        Counts how often a value occurs in an array.

     98        @param a the array

     99        @param value the value to count

    100        @return the number of occurrences of value in a

    101     */

    102     public static int count(int[] a, int value)

    103     {

    104        int count = 0;

    105        for (int i = 0; i < a.length; i++)

    106        {

    107           if (a[i] == value) { count++; }

    108        }

    109        return count;

    110     }

    111

    112     /**

    113        Computes the largest value of an array.

    114        @param a the array

    115        @return the largest value in a

    116     */

    117     public static int max(int[] values)

    118     {

    119        int largest = values[0];

    120        for (int i = 1; i < values.length; i++)

    121        {

    122           if (values[i] > largest)

    123           {

    124              largest = values[i];

    125           }

    126        }

    127        return largest;

    128     }

    129

    130     /**

    131        Finds a value in an array, using the linear search

    132        algorithm.

    133        @param a the array to search

    134        @param value the value to find

    135        @return the index at which the value occurs, or -1

    136        if it does not occur in the array

    137     */

    138     public static int search(int[] a, int value)

    139     {

    140        for (int i = 0; i < a.length; i++)

    141        {

    142           if (a[i] == value) { return i; }

    143        }

    144        return -1;

    145     }

    146  }